package lc_剑指_Offer_II_050_向下的路径节点之和;

import java.util.HashMap;
import java.util.Map;

public class Solution {

//      Definition for a binary tree node.
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	int targetSum;

	public int pathSum(TreeNode root, int targetSum) {
		this.targetSum = targetSum;
		Map<Long, Integer> cnts = new HashMap<>();
		cnts.put(0l, 1);
		return f(root, 0, cnts);
	}

	private int f(TreeNode root, long sum, Map<Long, Integer> cnts) {
		if (root == null) {
			return 0;
		}
		sum += root.val;
		int ans = cnts.getOrDefault(sum - targetSum, 0);
		cnts.merge(sum, 1, Integer::sum);
		ans += f(root.left, sum, cnts);
		ans += f(root.right, sum, cnts);
		cnts.merge(sum, -1, Integer::sum);
		return ans;
	}

}